BZOJ4355 Play with sequence < SegBeats >

Problem

Play with sequence

Description

维护一个长度为的序列，现在有三种操作：

给出参数，将都赋值为。
给出参数，对于区间里的每个数，将赋值为。
给出参数，输出里值为的数字个数。

Input

第一行包含两个正整数，分别表示序列长度和操作个数。
第二行包含个整数，其中第个数表示，描述序列的初始状态。
接下来行描述个操作，保证，对于操作，，对于操作，。

Output

输出若干行，每行一个整数，依次回答每个操作的问题。

Sample Input

Sample Output

Source

2016.1.1新加数据
鸣谢Claris

标签：SegBeats 线段树

Solution

参见吉老师的冬令营课件。

令二元组表示对于区间中的每个数先再，发现这样的二元组是可以合并的。
对于二元组和，前者在后者的前面出现，则合并起来变成。
维护每个区间的最小值、次小值、最小值个数即可。若某区间后最小值和次小值的大小关系未发生改变，那么不需要递归到子区间重新打擂。维护即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300000
#define INF (1LL<<50)
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
struct Tag {lnt x, c;} tag[MAX_N<<2];
struct Node {lnt mi1, mi2; int cnt, tot;} tr[MAX_N<<2];
Node operator + (Node a, Node b) {
    Node ret = (Node){0, 0, 0, a.tot+b.tot};
    if (a.mi1 == b.mi1) ret.mi1 = a.mi1, ret.cnt = a.cnt+b.cnt, ret.mi2 = min(a.mi2, b.mi2);
    else if (a.mi1 < b.mi1) ret.mi1 = a.mi1, ret.cnt = a.cnt, ret.mi2 = min(a.mi2, b.mi1);
    else ret.mi1 = b.mi1, ret.cnt = b.cnt, ret.mi2 = min(a.mi1, b.mi2); return ret;
}
Tag operator + (Tag a, Tag b) {return (Tag){max(a.x+b.x, -INF), max(a.c+b.x, b.c)};}
void build(int v, int s, int t) {
    tag[v] = (Tag){0, -INF};
    if (s == t) {read(tr[v].mi1), tr[v].mi2 = INF, tr[v].cnt = 1, tr[v].tot = 0; return;}
    build(v<<1, s, mid), build(v<<1|1, mid+1, t), tr[v] = tr[v<<1]+tr[v<<1|1];
}
void maintain(int v, Tag tg) ;
void downtag(int v) {
    tag[v<<1] = tag[v<<1]+tag[v], tag[v<<1|1] = tag[v<<1|1]+tag[v];
    maintain(v<<1, tag[v]), maintain(v<<1|1, tag[v]), tag[v] = (Tag){0, -INF};
}
void maintain(int v, Tag tg) {
    lnt tmi1 = max(max(tr[v].mi1+tg.x, tg.c), 0LL);
    lnt tmi2 = max(max(tr[v].mi2+tg.x, tg.c), 0LL);
    tmi1 = min(tmi1, INF), tmi2 = min(tmi2, INF);
    if (tr[v].mi2 == INF) tmi2 = INF;
    if (tmi1 < tmi2)
        tr[v].mi1 = tmi1, tr[v].mi2 = tmi2, 
        tr[v].tot = tmi1 ? 0 : tr[v].cnt;
    else downtag(v), tr[v] = tr[v<<1]+tr[v<<1|1];
}
void modify(int v, int s, int t, int l, int r, Tag tg) {
    if (s >= l && t <= r) {tag[v] = tag[v]+tg, maintain(v, tg); return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, tg);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, tg);
    tr[v] = tr[v<<1]+tr[v<<1|1];
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[v].tot;
    int ret = 0; downtag(v);
    if (l <= mid) ret += query(v<<1, s, mid, l, r);
    if (r >= mid+1) ret += query(v<<1|1, mid+1, t, l, r);
    tr[v] = tr[v<<1]+tr[v<<1|1]; return ret;
}
int main() {
    read(n), read(m), build(1, 1, n);
    while (m--) {
        int opt, l, r, x; read(opt), read(l), read(r);
        if (opt == 1) read(x), modify(1, 1, n, l, r, (Tag){-INF, x});
        if (opt == 2) read(x), modify(1, 1, n, l, r, (Tag){x, 0});
        if (opt == 3) printf("%d\n", query(1, 1, n, l, r));
    }
    return 0;
}